package gold.gold03;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 *
 */
public class S0802迷路的机器人 {
    /**
     * 77, 比较经典的使用visited数组进行剪枝的操作
     * 回溯, 撤回的时候把撤回的位置标记成不可执行, 不知道这种程度的剪枝会不会超时
     * 有点搞不清楚遍历到右下角的时候怎么终止这个迭代
     */
    public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
        if(obstacleGrid == null && obstacleGrid.length == 0 && obstacleGrid[0].length == 0) return null;
        int[][] route = new int[obstacleGrid.length + obstacleGrid[0].length - 1][2];
        if(!pathWithObstaclesHelp(obstacleGrid, route, 0, 0)) return new ArrayList<>();
        // if(isExist) System.out.println(Arrays.deepToString(route));
        List<List<Integer>> res = new LinkedList<>();
        for(int[] temp1: route){
            res.add(Arrays.asList(temp1[0], temp1[1]));
        }
        return res;
    }
    private boolean pathWithObstaclesHelp(int[][] obstacleGrid, int[][] route, int row, int col){
        if(row >= obstacleGrid.length || col >= obstacleGrid[0].length || obstacleGrid[row][col] == 1)
            return false;
        route[row + col][0] = row;
        route[row + col][1] = col;
        if(row == obstacleGrid.length - 1 && col == obstacleGrid[0].length - 1){
            return true;
        }
        boolean right = pathWithObstaclesHelp(obstacleGrid, route, row + 1, col);
        if(right) return true;
        boolean down = pathWithObstaclesHelp(obstacleGrid, route, row, col + 1);
        if(down) return true;
        // 一开始没写这句话, 相当于没有剪枝的dfs, 数据大了之后会超时
        obstacleGrid[row][col] = 1;
        return false;
    }
}
